import java.util.Stack;

public class Calculate {
    public static String calculate(String s) {
        //创建两个堆栈来存储数字和运算符
        Stack<String> values = new Stack<>();
        Stack<Character> operators = new Stack<>();
        StringBuilder value = new StringBuilder();

        //循环遍历传入的表达式
        //表达式的形式事例： 1+2/3*1/2
        for (int i = 0; i < s.length(); i++) {
            char s_temp = s.charAt(i);

            //如果该字符不是操作符，则将其添加到数字堆栈中
            if (s_temp != '+' && s_temp != '-' && s_temp != '×' && s_temp != '÷' && s_temp != '^')
                value.append(s_temp);
            else {
                //否则，将该数字压入数字堆栈并清除它
                values.push(value.toString());
                value = new StringBuilder();
                //如果操作符堆栈为空，则将操作符添加到其中
                if (operators.isEmpty())
                    operators.push(s_temp);
                    //否则，检查该操作符是否比操作符堆栈顶中的操作符的优先级低
                else {
                    while (!operators.isEmpty() && hasPrecedence(s_temp, operators.peek())) {
                        //如果是，则对数字堆栈中的两个值应用操作符
                        Fraction fraction2 = Fraction.parseFraction(values.pop());
                        Fraction fraction1 = Fraction.parseFraction(values.pop());
                        values.push(applyOperator(operators.pop(), fraction2, fraction1).toString());
                    }
                    //将操作符添加到操作符堆栈中
                    operators.push(s_temp);
                }
            }
        }

        //将计算出的值压入数字堆栈
        values.push(value.toString());

        //检查操作符堆栈是否为空
        //循环遍历操作符堆栈
        while (!operators.isEmpty()) {
            //从数字堆栈中弹出两个值
            Fraction fraction2 = Fraction.parseFraction(values.pop());
            Fraction fraction1 = Fraction.parseFraction(values.pop());
            //对这两个值应用运算符，并将结果压入数字堆栈
            values.push(applyOperator(operators.pop(), fraction2, fraction1).toString());
        }

        //返回表达式的结果
        return values.pop();
    }

    //获取操作符的优先级
    private static int getPrecedence(char operator) {
        switch (operator) {
            case '+':
            case '-':
                return 1;
            case '×':
            case '÷':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }

    /**
     * 用于比较优先级高低
     * @param operator1 操作符1
     * @param operator2 操作符2
     * @return 返回是否 操作符1 比 操作符2 的优先级低
     */
    private static boolean hasPrecedence(char operator1, char operator2) {
        return getPrecedence(operator1) <= getPrecedence(operator2);
    }

    /**
     * 对两个数应用该操作符
     * @param operator 对这两个数所使用的操作符
     * @param b 数字1
     * @param a 数字2
     * @return 返回计算后的结果
     */
    private static Fraction applyOperator(char operator, Fraction b, Fraction a) {
        switch (operator) {
            case '+':
                return a.add(b);
            case '-':
                return a.subtract(b);
            case '×':
                return a.multiply(b);
            case '^':
                return a.power(b);
            case '÷':
                if (b.equals(Fraction.ZERO)) {
                    throw new ArithmeticException("Division by zero");
                }
                return a.divide(b);
        }
        return Fraction.ZERO;
    }
}
